4 决策树

#DecisionTree #InformationGain #MutualInformation #ID3 #Entropy #Pruning #CART #RegressionTree #Gini

1 决策树模型与学习

1.1 决策树模型

决策树

分类决策树模型是一种对实例分类的树形结构, 由结点, 有向边构成. 结点分为内部结点和叶结点, 分别代表特征/属性, 与类. Pasted image 20240816113405.png|300

决策树的内部结点对应着分类规则, 要求互斥且完备.

2 特征选择

2.1 信息增益

熵表示随机变量不确定性的度量. 设 $X$ 的概率分布为 $P (X = x_{i}) = p_{i}, 1 \leq i \leq n$ , 则 $X$ 的熵定义为 $H (X) = - \sum_{i = 1}^{n} p_{i} \log p_{i} .$ 也可记为 $H (p)$ . 从定义可验证 $0 \leq H (p) \leq \log n .$

推导

根据对数和不等式 $\sum_{i = 1}^{n} (a_{i} \log \frac{a_{i}}{b_{i}}) \leq \sum_{i = 1}^{n} a_{i} \cdot \log \frac{\sum_{i = 1}^{n} a_{i}}{\sum_{i = 1}^{n} b_{i}},$
结合均值不等式得 $H (p) = \sum_{i = 1}^{n} p_{i} \log \frac{1}{p_{i}} \leq \log \frac{1}{\sum_{i = 1}^{n} p_{i}^{- 1}} \leq \log n .$

如果

X \sim Bernoulli (p)

此时 $H (p) = - p \log p - (1 - p) \log (1 - p)$ , 可以通过求导找到最大值点.

如果随机变量 $(X, Y)$ 有联合分布 $P (X = x_{i}, Y = y_{j}) = p_{i j}, 1 \leq i \leq n, 1 \leq j \leq m$ , 则条件熵 $H (Y | X) = \sum_{i = 1}^{n} p_{i} H (Y | X = x_{i}) .$
定义 $H (Y) - H (Y | X)$ 为互信息.

信息增益

特征 $A$ 对训练集 $D$ 的信息增益为 $g (D, A) = H (D) - H (D | A) .$

设训练集为 $D$ , 有 $K$ 个类 $C_{1}, \dots, C_{K}$ , 自然地 $\sum_{k = 1}^{K} | C_{K} | = | D |$ . 设特征 $A$ 有 $n$ 个不同的取值 ${a_{1}, \dots, a_{n}}$ . 根据 $A$ 的取值将 $D$ 划分为 $n$ 个子集 $D_{1}, \dots, D_{n}$ , 自然地 $\sum_{i = 1}^{n} | D_{i} | = | D |$ . 记 $D_{i k} = D_{i} \cap C_{k}$ . 下面给出信息增益算法

信息增益算法

输入: $D, A$ .
输出: $A$ 对 $D$ 的信息增益 $g (D, A)$ .

计算经验熵 $H (D) = - \sum_{k = 1}^{K} \frac{| C_{k} |}{| D |} \log_{2} \frac{| C_{k} |}{| D |} .$
计算经验条件熵 $H (D | A) = \sum_{i = 1}^{n} \frac{| D_{i} |}{| D |} H (D_{i}) = - \sum_{i = 1}^{n} \frac{| D_{i} |}{| D |} \sum_{k = 1}^{K} \frac{| D_{i k} |}{| D_{i} |} \log_{2} \frac{| D_{i k} |}{| D_{i} |} .$
计算信息增益 $g (D, A) = H (D) - H (D | A) .$

我们可以从若干特征中选择信息增益最大的那个特征.

2.2 信息增益比

信息增益倾向于选择取值较多的特征. 信息增益比将会校正这个问题.

信息增益

$g_{R}(D,A)=\frac{g(D,A)}{H_{A}(D)},$$ 其中根据信息增益算法, $H_{A}(D)=-\sum_{i=1}^{n}\frac{|D_{i}|}{|D|}\log_{2}\frac{|D_{i}|}{|D|}$, $n$ 是 $A$ 取值的个数.$

3 决策树的生成

3.1 ID3 算法

算法的核心是在决策树各个结点上应用信息增益准则来选择特征.

ID3算法

输入: 训练集 $D$ , 特征集 $A$ , 阈值 $ε$ .
输出: 决策树 $T$ .

若 $D$ 的所有实例属于同一类 $C_{k}$ , 则 $T$ 为单结点树.
若 $A = \emptyset$ , 则 $T$ 为单结点树.
否则按照信息增益算法计算并选择信息增益最大的特征 $A_{g}$ .
如果 $A_{g}$ 的增益小于 $ε$ , 则 $T$ 为单结点树.
否则对 $A_{g}$ 的每一个值 $a_{i}$ , 按照 $A_{g} = a_{i}$ 把 $D$ 分割为 $D_{i}$ 构建子节点.
对第 $i$ 个子节点, 以 $D_{i}$ 为训练集, $A - {A_{g}}$ 为特征集, 递归地调用 1~5 得到子树 $T_{i}$ .

该算法容易产生过拟合.

3.2 C4.5 的生成算法

信息增益换成了信息增益比, 其他没变.

C4.5的生成算法

输入: 训练集 $D$ , 特征集 $A$ , 阈值 $ε$ .
输出: 决策树 $T$ .

若 $D$ 的所有实例属于同一类 $C_{k}$ , 则 $T$ 为单结点树.
若 $A = \emptyset$ , 则 $T$ 为单结点树.
否则按照信息增益比计算并选择信息增益最大的特征 $A_{g}$ .
如果 $A_{g}$ 的增益小于 $ε$ , 则 $T$ 为单结点树.
否则对 $A_{g}$ 的每一个值 $a_{i}$ , 按照 $A_{g} = a_{i}$ 把 $D$ 分割为 $D_{i}$ 构建子节点.
对第 $i$ 个子节点, 以 $D_{i}$ 为训练集, $A - {A_{g}}$ 为特征集, 递归地调用 1~5 得到子树 $T_{i}$ .

4 决策树的剪枝

假设树 $T$ 的叶节点个数为 $| T |$ , $t$ 是 $T$ 的叶结点, 上面有 $N_{t}$ 个样本点, 其中 $k$ 类样本点有 $N_{t k}$ 个, $H_{t} (T)$ 为 $t$ 的经验熵, 则损失函数定义为 $\begin{matrix} (4.1) & C_{α} (T) = \sum_{t = 1}^{| T |} N_{t} H_{t} (T) + α | T |, \end{matrix}$ 其中 $H_{t} (T) = - \sum_{k = 1}^{K} \frac{N_{t k}}{N_{t}} \log \frac{N_{t k}}{N_{t}} .$
把 (4.1) 的第一项记为 $C (T) = \sum_{t}^{| T |} N_{t} H_{t} (T) = - \sum_{t = 1}^{| T |} \sum_{k = 1}^{K} N_{t k} \log \frac{N_{t k}}{N_{t}},$ 则 $C_{α} (T) = C (T) + α | T | .$

剪枝算法

输入: 生成算法产生的树 $T$ , $α$ .
输出: 修建后的子树 $T_{α}$ .

计算每个节点的经验熵.
递归的从树的叶结点向上回缩. 设一组叶结点回缩到父结点后整体树分别为 $T_{B}, T_{A}$ , 对应的损失函数分别为 $C_{α} (T_{B}), C_{α} (T_{A})$ . 如果 $C_{α} (T_{A}) \leq C_{α} (T_{B}),$ 则进行剪枝, 把父结点变成新的叶结点.
返回 2, 直到不能继续, 得到 $T_{α}$ .

5 CART 算法

即分类与回归树模型(classification and regression tree, CART ) 既可以用于分类也可以用于回归. 在给定 $X$ 的条件下输出 $Y$ 的条件概率分布. 假设了决策树是二叉树, 内部结点的取值是是/否.
大体上包含了两个部分:

生成: 用训练集生成尽可能大的决策树;
剪枝: 用测试集剪枝, 尽可能最小化损失函数.

5.1 CART 生成

5.1.1 回归树的生成

设 $X, Y$ 分别为输入和输出变量, 并且 $Y$ 是连续变量. 给定 $D = {(x_{1}, y_{1}), \dots, (x_{N}, y_{N})}$ .
一棵回归树对应特征空间的一个划分. 假设划分为 $R_{1}, \dots, R_{M}$ , 在每个单元 $R_{m}$ 上有固定的输出值 $c_{m}$ , 于是回归树模型可以表示为 $f (x) = \sum_{m = 1}^{M} c_{m} I (x \in R_{m}) .$
此时可以用平方误差 $\sum_{x_{i} \in R_{m}} (y_{i} - f (x_{i}))^{2}$ 来衡量误差, 并希望它最小. 容易知道 ${\hat{c}}_{m} = ave (y_{i} | x_{i} \in R_{m}) .$
接下来讨论划分. 选择第 $j$ 个变量 $x^{(j)}$ 和它的值 $s$ 作为切分变量和切分点, 定义 $R_{1} (j, s) = {x | x^{(j)} \leq s}, R_{2} (j, s) = {x | x^{(j)} > s} .$ 然后求解 $\begin{matrix} (5.1) & min_{j, s} [min_{c_{1}} \sum_{x_{i} \in R_{1} (j, s)} (y_{i} - c_{1})^{2} + min_{c_{2}} \sum_{x_{i} \in R_{2} (j, s)} (y_{i} - c_{2})^{2}], \end{matrix}$
然后对固定的 $j$ 找到最优切分点 $s$ . 这样 ${\hat{c}}_{1} = ave (y_{i} | x_{i} \in R_{1} (j, s)), {\hat{c}}_{2} = ave (y_{i} | x_{i} \in R_{2} (j, s)) .$ 对每个区域重复上述划分过程.

最小二乘回归树生成算法

输入: $D$
输出: 回归树 $f (x)$ .

求解 (5.1), 找到 $(j, s)$ .
用选定的 $(j, s)$ 划分区域, $\begin{aligned} R_{1} (j, s) = {x | x^{(j)} \leq s}, R_{2} (j, s) = {x | x^{(j)} > s}, \\ {\hat{c}}_{m} = \frac{1}{N_{m}} \sum_{x_{i} \in R_{m} (j, s)} y_{i}, x \in R_{m}, m = 1, 2. \end{aligned}$
继续对两个子区域调用 1, 2, 直到满足条件.
依据划分的 $M$ 个区域 $R_{1}, \dots, R_{M}$ , 生成决策树 $f (x) = \sum_{m = 1}^{M} {\hat{c}}_{m} I (x \in R_{m}) .$

5.1.2 分类树的生成

Gini指数

分类问题中, 假设有 $K$ 个类, 样本点属于第 $k$ 类的概率为 $p_{k}$ , 则 $Gini (p) = \sum_{k = 1}^{K} p_{k} (1 - p_{k}) = 1 - \sum_{k = 1}^{K} p_{k}^{2} .$
特别地, 二分类问题的 Gini 指数为 $Gini (p) = 2 p (1 - p)$ .
对于给定的样本集合 $D$ , $Gini (D) = 1 - \sum_{k = 1}^{K} {(\frac{| C_{k} |}{| D |})}^{2} .$

从概率意义上, 它等于从样本中采样两个点, 它们不在同一类的概率.